package com.glb.leetcode;

import java.util.Arrays;

public class HB_test4 {
  public static void main(String[] args) {
    // 默认 weight, value 需要有排序.
    int[] weight = { 1, 2, 3, 4 };
    int[] value = { 15, 20, 30, 40 };
    int bagSize = 7;
    testWeightBagProblem(weight, value, bagSize);
  }

  /**
   * 动态规划获得结果
   * 
   * @param weight  物品的重量
   * @param value   物品的价值
   * @param bagSize 背包的容量
   */
  public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {
    // 创建dp数组
    int weightLength = weight.length; // 获取物品的数量
    int[][] dp = new int[weightLength][bagSize + 1]; // TODO, 为什么要 +1 ? Answer: 刚好达到临界点时的值

    // 初始化dp数组
    // 创建数组后，其中默认的值就是 0
    // 从 weight 最小值的下标开始赋值
    for (int j = weight[0]; j <= bagSize; j++) {
      dp[0][j] = value[0];
    }

    // 填充dp数组
    for (int i = 1; i < weight.length; i++) {
      for (int j = 1; j <= bagSize; j++) {
        if (j < weight[i]) {
          /**
           * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
           * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
           */
          dp[i][j] = dp[i - 1][j];
        } else {
          /**
           * 当前背包的容量可以放下物品i
           * 那么此时分两种情况：
           * 1、不放物品i (dp[i - 1][j])
           * 2、放物品i
           * 比较这两种情况下，哪种背包中物品的最大价值最大
           */
          int tempValue = dp[i - 1][j - weight[i]];  
          // value[i]   现在物品的重量
          System.out.println("tempValue: " + tempValue + ", dp["+ (i-1) + "][" + (j-weight[i]) + "]");
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
      }
    }

    System.out.println(Arrays.deepToString(dp));
    // 打印dp数组
    for (int i = 0; i < weightLength; i++) {
      for (int j = 0; j <= bagSize; j++) {
        System.out.print(dp[i][j] + ", ");
      }
      System.out.println("\n");
    }

    System.out.println("result:" + dp[weightLength-1][bagSize]);
  }

}
